#pragma GCC optimize(3)
#pragma G++ optimize(3)
#include<iostream>
#include<ctime>
#include<random>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
#define MAXN 200
#define MAXM 200
#define MAXGROUP 8050
#define MAXNUMBER 100000000

#define BATCH_SIZE 20
// g++ -O3 ga.cpp -std=c++14 -o ga
// ./ga < data.txt
/* ************************************* */
/* open debug */
#define show_train_log 1
#undef show_train_log

#define show_log 0
// #undef show_log
/* ************************************ */

using namespace std;
// 
int n, m, group_num=2000, epoch_num=100, sz = 0, variation_coe=5, repeat_times=1, tabu_step = 20, seed=2;
unordered_map<unsigned long long, int> tabu_mp;
double coe = 4;
random_device rd;
// mt19937 rng(rd());
mt19937 rng(seed);
double x;
int midx[MAXN][MAXN][MAXM], mmtime[MAXN][MAXN][MAXM];
// steps[i] 零件i的工序数量
int steps[MAXN], stepm[MAXN][MAXN];
struct Seq{
    vector<int> pso;
    int val;
    bool operator<(const Seq& other) const { return val < other.val;}
}ans, groups[BATCH_SIZE][2][MAXGROUP];

struct T2{
    int start_time, finish_time, n_idx, step_idx;

}mach[MAXM][MAXN * MAXN];
void init(){
    ans.val = MAXNUMBER;
    scanf("%d %d %lf",&n,&m,&x);
    for (int i = 0; i < n; i++) {
        scanf("%d",&steps[i]);
        sz += steps[i];
        for (int j = 0; j < steps[i]; j++){
            scanf("%d",&stepm[i][j]);
            for (int k = 0; k < stepm[i][j]; k++){
                scanf("%d %d",&midx[i][j][k],&mmtime[i][j][k]);
                // midx[i][j][k] -= 1;
            }
        }
    }
    // srand(time(0));
    srand(seed);
    tabu_mp.clear();
}

unsigned int Hash1(Seq &t) {
  unsigned int hash = 0;
  for(auto &now:t.pso) {
    hash = now + (hash<<6) + (hash<<16) - hash;
  }
  return (hash & 0x7FFFFFFF);
}

unsigned int Hash2(Seq &t) {
  unsigned int hash = 1315423911;
  for(auto &now:t.pso) {
    hash^=((hash << 5) + now + (hash>>2));
  }
  return (hash & 0x7FFFFFFF);
}

unsigned long long Hash(Seq &t) {
    return (((unsigned long long)Hash1(t)) << 32) | Hash2(t);
}

Seq get_random_pso(){
    Seq t;
    t.pso.reserve(sz);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < steps[i]; j++){
            t.pso.push_back(i);
        }
    }
    assert(t.pso.size()==sz);
    shuffle(t.pso.begin(), t.pso.end(), rng);
    return std::move(t);
}

void calc(Seq &t){
    int mst[m], per[n], pst[n], final_time = 0;
    memset(mst, 0, sizeof(mst));
    memset(per, 0, sizeof(per));
    memset(pst, 0, sizeof(pst));
    for (int i = 0; i < sz; i++){
        int person = t.pso[i];
        int step = pst[t.pso[i]];
        int best_time = -1, best_machine = -1, best_start_time = -1, best_pos = -1;
        for (int l = 0; l < stepm[person][step]; l++){
            int machine = midx[person][step][l];
            int time = mmtime[person][step][l];
            int pos = -1, now = per[person];
            for (int j = 0; j < mst[machine]; j++){
                if (now + time <= mach[machine][j].start_time){
                    pos = j;
                    if (now + time < best_time || best_time == -1){
                        best_start_time = now;
                        best_time = now + time;
                        best_machine = machine;
                        best_pos = j;
                    }
                    break;
                }else{
                    now = max(now, mach[machine][j].finish_time);
                }
            }
            if (pos == -1){
                if (now + time < best_time || best_time == -1){
                    best_start_time = now;
                    best_time = now + time;
                    best_machine = machine;
                    best_pos = -1;
                }
            }
        }
        if (best_time == -1){
            cout << "error!" << endl;
        }
        if (best_pos == -1){
            mach[best_machine][mst[best_machine]] = T2{best_start_time,best_time,person,step};
            mst[best_machine] += 1;
            per[person] = best_time;
            pst[person] += 1;
        }else{
            for (int k = mst[best_machine]; k > best_pos; k--){
                mach[best_machine][k] = mach[best_machine][k - 1];
            }
            mach[best_machine][best_pos] = T2{best_start_time,best_time,person,step};
            mst[best_machine] += 1;
            per[person] = best_time;
            pst[person] += 1;
        }
    }
    for (int i = 0; i < n; i++) final_time = max(final_time, per[i]);
    t.val = final_time;
}

#define random_select() (rand() % group_num)
Seq variation(Seq &t){
    Seq output;
    int idx = rand() % sz;
    int idx2 = rand() % sz;
    output.pso.reserve(sz);
    // output.pso.resize(steps[idx],idx);
    // for (int i = 0; i < sz; i++){
    //     if (t.pso[i] != idx){
    //         output.pso.push_back(t.pso[i]);
    //     }
    // }
    if (idx > idx2){
        int tmp = idx;
        idx = idx2;
        idx2 = tmp;
    }
    for (int i = 0; i < idx; i++) output.pso.push_back(t.pso[i]);
    for (int i = idx2; i >= idx; i--) output.pso.push_back(t.pso[i]);
    for (int i = idx2 + 1; i < sz; i++) output.pso.push_back(t.pso[i]);
    assert(output.pso.size()==sz);
    return std::move(output);
}
pair<Seq,Seq> cross(Seq &t1, Seq &t2){
    Seq output, output2;
    output.pso.reserve(sz);
    output2.pso.reserve(sz);
    int line = sz / 4 + rand() % (sz / 2);
    int per[n];
    memset(per, 0, sizeof(per));
    for (int i = 0; i < line; i++){
        output.pso.push_back(t1.pso[i]);
        per[t1.pso[i]] += 1;
    }
    for (int i = 0; i < sz; i++){
        int person = t2.pso[i];
        per[person] -= 1;
        if (per[person] < 0) {
            output.pso.push_back(person);
        }else{
            output2.pso.push_back(person);
        }
    }
    for (int i = line; i < sz; i++){
        output2.pso.push_back(t1.pso[i]);
    }
    assert(output.pso.size()==sz && output2.pso.size()==sz);
    return std::move(make_pair(std::move(output),std::move(output2)));
}
void GA(Seq (&groups)[2][MAXGROUP]) {
    // init group
    bool now = 0;
    for (int i = 0; i < group_num * coe; i++){
        groups[0][i] = get_random_pso();
    }
    for (int i = 0; i < epoch_num; i++){
        int epoch_total = 0, group_best = MAXNUMBER;
        for (int j = 0; j < group_num * coe; j++){
            calc(groups[now][j]);
            if (groups[now][j].val < ans.val){
                ans.val = groups[now][j].val;
                ans.pso = groups[now][j].pso;
            }
            group_best = min(group_best, groups[now][j].val);
            epoch_total += groups[now][j].val;
        }
#ifdef show_train_log
        cout << i << ":avg-" << epoch_total * 1.0 / group_num / coe;
        cout << " group_best-" << group_best;
        cout << " history_best-" << ans.val << endl;
#endif
        sort(groups[now], groups[now] + (int)(group_num * coe));
        int j = 0;
        while (j < group_num * coe){
            int number = rand() % 10;
            int rd_idx = random_select();
            if (number <= variation_coe){
                groups[1^now][j] = variation(groups[now][rd_idx]);
                unsigned long long h = Hash(groups[1^now][j]);
                if (tabu_mp.count(h) == 0 || i - tabu_mp[h] >= tabu_step){
                    j += 1;
                    tabu_mp[h] = i;
                }
            }else{
                int rd_idx2 = random_select();
                auto tmp = cross(groups[now][rd_idx], groups[now][rd_idx2]);
                groups[1^now][j] = std::move(tmp.first);
                unsigned long long h = Hash(groups[1^now][j]);
                if (tabu_mp.count(h) == 0 || i - tabu_mp[h] >= tabu_step){
                    j += 1;
                    tabu_mp[h] = i;
                }
                groups[1^now][j] = std::move(tmp.second);
                h = Hash(groups[1^now][j]);
                if (tabu_mp.count(h) == 0 || i - tabu_mp[h] >= tabu_step){
                    j += 1;
                    tabu_mp[h] = i;
                }
                
            }
        }
        now ^= 1;
    }
    if (show_log) cout << "best time: " << ans.val << endl;
}

// TODO
void batch_GA() {


}
string machine_to_str(int number){
    if (number <= 9) return "00" + to_string(number);
    if (number <= 99) return "0" + to_string(number);
    return to_string(number);
}
string step_to_str(int number){
    if (number <= 9) return "0" + to_string(number);
    return to_string(number);
}
void output(){
    int mst[m], per[n], pst[n], final_time = 0;
    memset(mst, 0, sizeof(mst));
    memset(per, 0, sizeof(per));
    memset(pst, 0, sizeof(pst));
    for (int i = 0; i < sz; i++){
        int person = ans.pso[i];
        int step = pst[ans.pso[i]];
        int best_time = -1, best_machine = -1, best_start_time = -1, best_pos = -1;
        for (int l = 0; l < stepm[person][step]; l++){
            int machine = midx[person][step][l];
            int time = mmtime[person][step][l];
            int pos = -1, now = per[person];
            for (int j = 0; j < mst[machine]; j++){
                if (now + time <= mach[machine][j].start_time){
                    pos = j;
                    if (now + time < best_time || best_time == -1){
                        best_start_time = now;
                        best_time = now + time;
                        best_machine = machine;
                        best_pos = j;
                    }
                    break;
                }else{
                    now = max(now, mach[machine][j].finish_time);
                }
            }
            if (pos == -1){
                if (now + time < best_time || best_time == -1){
                    best_start_time = now;
                    best_time = now + time;
                    best_machine = machine;
                    best_pos = -1;
                }
            }
        }
        if (best_time == -1){
            cout << "error!" << endl;
        }
        if (best_pos == -1){
            mach[best_machine][mst[best_machine]] = T2{best_start_time,best_time,person,step};
            mst[best_machine] += 1;
            per[person] = best_time;
            pst[person] += 1;
        }else{
            for (int k = mst[best_machine]; k > best_pos; k--){
                mach[best_machine][k] = mach[best_machine][k - 1];
            }
            mach[best_machine][best_pos] = T2{best_start_time,best_time,person,step};
            mst[best_machine] += 1;
            per[person] = best_time;
            pst[person] += 1;
        }
    }
    for (int i = 0; i < n; i++) final_time = max(final_time, per[i]);
    ans.val = final_time;
    
    // for (int i = 0; i < m; i++){
    //     cout << "M" << i + 1 << ":";
    //     for (int j = 0; j < mst[i]; j++){
    //         if (j != 0) cout << ",";
    //         cout << "(";
    //         string s = "S" + machine_to_str(mach[i][j].n_idx + 1);
    //         cout << s << ",";
    //         cout << s + step_to_str(mach[i][j].step_idx + 1) << ",";
    //         cout << mach[i][j].start_time << ",";
    //         cout << mach[i][j].finish_time;
    //         cout << ")";
    //     }
    //     cout << endl;
    // }
    cout << "seed: " << seed << " sol is: " << ans.val << endl;
}
int main(){
    double begin = (double)clock() / CLOCKS_PER_SEC;
    init();
    for (int i = 0; i < repeat_times; i++) GA(groups[1]);
    output();
    double end = (double)clock() / CLOCKS_PER_SEC;
    // cout << "running time: " << end - begin << "s" << endl;
    return 0;
}